#include<iostream>
#include<vector>
using namespace std;
int dp(vector<vector<int>> obstacleGrid)
{
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();
    if(obstacleGrid[0][0]||obstacleGrid[m-1][n-1])
        return 0;
    vector<vector<int>> dp(m,vector<int>(n));
    //dp数组初始化
    //行初始化
    for(int i=0;i<m;i++)
    {
        //若遇到障碍，则障碍以及障碍正下方的全部初始化为0
        if(obstacleGrid[i][0])
            break;
        dp[i][0] = 1;
    }
    //列初始化
    for(int i=0;i<n;i++)
    {
        if(obstacleGrid[0][i])
            break;
        dp[0][i] = 1;
    }
    for(int i=1;i<m;i++)
    {
        for(int j=1;j<n;j++)
        {
            if(!obstacleGrid[i][j])
            {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
                //cout<<dp[i][j]<<" ";
            }
        }
        //cout<<endl;
    }
    return dp[m-1][n-1];
}
int main()
{
    cout<<"enter two number:"<<endl;
    int m,n;
    cin>>m>>n;
    vector<vector<int>> obstacleGrid(m,vector<int>(n));
    cout<<"enter"<<m<<"*"<<n<<"martix:"<<endl;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
            cin>>obstacleGrid[i][j];
    }
    cout<<"the result is:"<<dp(obstacleGrid)<<endl;
    return 0;
}